/*
https://leetcode.cn/problems/longest-univalue-path/description/
687. 最长同值路径
方钊堉 2024.11.6
dfs
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* rootNode) {
        // 开始深度优先搜索
        dfs(rootNode);
        // 结果需要减一，因为路径的定义是边的数量而不是节点数量
        return maxLength - 1;
    }

private:
    int maxLength = 1; // 记录最长的同值路径长度（以节点数计算）

    int dfs(TreeNode* currentNode) {
        if (!currentNode) return 0; // 如果节点为空，则返回0
        
        // 如果是叶子节点，直接返回1
        if (!currentNode->left && !currentNode->right) return 1;

        int currentLength = 0; // 当前节点贡献的最大长度
        int currentPathLength = 1; // 包括当前节点在内的路径长度

        // 递归计算左子树的最长同值路径
        int leftLength = dfs(currentNode->left);
        // 递归计算右子树的最长同值路径
        int rightLength = dfs(currentNode->right);

        // 如果左子节点存在且与当前节点值相同
        if (currentNode->left && currentNode->left->val == currentNode->val) {
            currentPathLength += leftLength; // 更新当前路径长度
            currentLength = max(currentLength, leftLength); // 更新当前节点贡献的最大长度
        }
        // 如果右子节点存在且与当前节点值相同
        if (currentNode->right && currentNode->right->val == currentNode->val) {
            currentPathLength += rightLength; // 更新当前路径长度
            currentLength = max(currentLength, rightLength); // 更新当前节点贡献的最大长度
        }
        // 更新全局最长同值路径长度
        maxLength = max(maxLength, currentPathLength);
        // 返回当前节点贡献的最大长度+1（包括当前节点）
        return currentLength + 1;
    }
};